package kgame5.kgu.move.quadtree {
import kgame5.k3d.core.obj3d.hardvo.HardVO;
import kgame5.kutil.T;

import flash.display.Sprite;

/**
 * @author kk
 * 2048,单元格子64,则需要7层
 * 
 * 如果是出现重叠的物体，则四叉树不好处理
 * 
 * 用法，
 * 1,构造四叉树Insert。障碍物是四叉树
 * 几本的功能，添加，删除，查找
 * 2,有一个不在四叉树里的东西移动了,执行Process(hardVO);//这样
 * 
 * 这个其实是个容器，就跟array,hashMap一样的
 */
public class QuadTree {
	
	public static const MAX_DEPTH:int=5;
	
	public var root:QuadTreeNode;
	
	//边界值，不能用minX,maxX做
	public var 
		left:int,
		right:int,
		up:int,
		down:int;
	
	public function QuadTree(x:int,z:int,w:int,h:int){
		root=new QuadTreeNode(x,z,w,h);
		
		left=x;
		right=x+w;
		up=z;
		down=z-h;
	}
	
	public function Insert(node:QuadTreeNode,vo:HardVO){
		//--1:如果是最大深度，则直接放到此物体里
		if(node.depth==MAX_DEPTH){
			node.listObj.push(vo);
			return;
		}
		
		//--2:检测被完全包围在哪个象限
		//0
		if(node.rect0.contains(vo)){
			_insertToAQuad(node,vo,0);//递归插入到一个象限去
			return;
		}
		//1
		if(node.rect1.contains(vo)){
			_insertToAQuad(node,vo,1);//递归插入到一个象限去
			return;
		}
		//2
		if(node.rect2.contains(vo)){
			_insertToAQuad(node,vo,2);//递归插入到一个象限去
			return;
		}
		//3
		if(node.rect3.contains(vo)){
			_insertToAQuad(node,vo,3);//递归插入到一个象限去
			return;
		}
		
		//--3:不包含在任何象限里的，则放入node的listObj中
		node.listObj.push(vo);
		
		//-设置一下vo的数值,测试用的
		//vo.dataObj = node.depth;
	}

	private function _insertToAQuad(node:QuadTreeNode,vo:HardVO,quadIdx:int){
		var childNode:QuadTreeNode;
		
		//如果无此节点，则创建新的
		if(node.aChildNode[quadIdx]==null){//如果没有则创建一个
			node.addChildNode(quadIdx);
		}
			
		childNode = node.aChildNode[quadIdx];//取出此节点
			
		//递归插入
		this.Insert(childNode, vo);
	}
	
	//查找
	public function Find(node:QuadTreeNode,vo:HardVO):QuadTreeNode{
		//--1:如果已经是最深的，返回
		if(node.depth==MAX_DEPTH){
			return node;
		}
		//--2:如果在某一象限，则递归
		if(node.aChildNode[0]!=null&&node.rect0.contains(vo)){
			return Find(node.aChildNode[0],vo);
		}
		if(node.aChildNode[1]!=null&&node.rect1.contains(vo)){
			return Find(node.aChildNode[1],vo);
		}
		if(node.aChildNode[2]!=null&&node.rect2.contains(vo)){
			return Find(node.aChildNode[2],vo);
		}
		if(node.aChildNode[3]!=null&&node.rect3.contains(vo)){
			return Find(node.aChildNode[3],vo);
		}
		//--3：如果不在子象限，则在此node内
		return node;
	}
	
	//删除,不需要太高的性能
	public function Remove(vo:HardVO){
		T.p(this,"Remove");
		//找到包含此vo的分支
		var node:QuadTreeNode=Find(root,vo);
		if(node==null){
			T.p("Remove删除失败,找不到此节点");
			return;
		}
		//从物品列表删除
		for(var i:int=0;i<node.listObj.length;i++){
			if(node.listObj[i]==vo){
				T.p("找到了目标，删除了！");
				node.listObj.splice(i,1);
				return;
			}
		}
	}
	
	
	//创建一个mc来描述四叉树
	public function dump():Sprite{
		return root.dump();
	}
}//end of class
}
